{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Single-Threaded CPU"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单线程 CPU"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维数组 <code>tasks</code> ，用于表示 <code>n</code>​​​​​​ 项从 <code>0</code> 到 <code>n - 1</code> 编号的任务。其中 <code>tasks[i] = [enqueueTime<sub>i</sub>, processingTime<sub>i</sub>]</code> 意味着第 <code>i<sup>​​​​​​</sup></code>​​​​ 项任务将会于 <code>enqueueTime<sub>i</sub></code> 时进入任务队列，需要 <code>processingTime<sub>i</sub></code><sub> </sub>的时长完成执行。</p>\n",
    "\n",
    "<p>现有一个单线程 CPU ，同一时间只能执行 <strong>最多一项</strong> 任务，该 CPU 将会按照下述方式运行：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。</li>\n",
    "\t<li>如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择 <strong>执行时间最短</strong> 的任务开始执行。如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。</li>\n",
    "\t<li>一旦某项任务开始执行，CPU 在 <strong>执行完整个任务</strong> 前都不会停止。</li>\n",
    "\t<li>CPU 可以在完成一项任务后，立即开始执行一项新任务。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em> </em>CPU<em> </em>处理任务的顺序。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>tasks = [[1,2],[2,4],[3,2],[4,1]]\n",
    "<strong>输出：</strong>[0,2,3,1]\n",
    "<strong>解释：</strong>事件按下述流程运行： \n",
    "- time = 1 ，任务 0 进入任务队列，可执行任务项 = {0}\n",
    "- 同样在 time = 1 ，空闲状态的 CPU 开始执行任务 0 ，可执行任务项 = {}\n",
    "- time = 2 ，任务 1 进入任务队列，可执行任务项 = {1}\n",
    "- time = 3 ，任务 2 进入任务队列，可执行任务项 = {1, 2}\n",
    "- 同样在 time = 3 ，CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ，可执行任务项 = {1}\n",
    "- time = 4 ，任务 3 进入任务队列，可执行任务项 = {1, 3}\n",
    "- time = 5 ，CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ，可执行任务项 = {1}\n",
    "- time = 6 ，CPU 完成任务 3 并开始执行任务 1 ，可执行任务项 = {}\n",
    "- time = 10 ，CPU 完成任务 1 并进入空闲状态\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]\n",
    "<strong>输出：</strong>[4,3,2,0,1]\n",
    "<strong>解释：</strong>事件按下述流程运行： \n",
    "- time = 7 ，所有任务同时进入任务队列，可执行任务项  = {0,1,2,3,4}\n",
    "- 同样在 time = 7 ，空闲状态的 CPU 开始执行任务 4 ，可执行任务项 = {0,1,2,3}\n",
    "- time = 9 ，CPU 完成任务 4 并开始执行任务 3 ，可执行任务项 = {0,1,2}\n",
    "- time = 13 ，CPU 完成任务 3 并开始执行任务 2 ，可执行任务项 = {0,1}\n",
    "- time = 18 ，CPU 完成任务 2 并开始执行任务 0 ，可执行任务项 = {1}\n",
    "- time = 28 ，CPU 完成任务 0 并开始执行任务 1 ，可执行任务项 = {}\n",
    "- time = 40 ，CPU 完成任务 1 并进入空闲状态</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>tasks.length == n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= enqueueTime<sub>i</sub>, processingTime<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [single-threaded-cpu](https://leetcode.cn/problems/single-threaded-cpu/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [single-threaded-cpu](https://leetcode.cn/problems/single-threaded-cpu/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,4],[3,2],[4,1]]', '[[7,10],[7,12],[7,5],[7,4],[7,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n=len(tasks)\n",
    "        a=list(range(n))  #index<=>timestart\n",
    "        a.sort(key=lambda x: tasks[x][0])\n",
    "        time,ptr=1,0\n",
    "        c,q=[],[]\n",
    "        for i in range(n):\n",
    "            if not q:\n",
    "                time=max(time,tasks[a[ptr]][0])\n",
    "            while ptr<n and tasks[a[ptr]][0]<=time:\n",
    "                heapq.heappush(q, (tasks[a[ptr]][1], a[ptr]))\n",
    "                ptr+=1\n",
    "            proc,index=heapq.heappop(q)\n",
    "            time+=proc\n",
    "            c.append(index)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        import heapq\n",
    "        n = len(tasks)\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda x: tasks[x][0])\n",
    "\n",
    "        res = []\n",
    "        h = []\n",
    "        time = 0\n",
    "        cur = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if not h:\n",
    "                time = max(time, tasks[indices[cur]][0])\n",
    "            while cur < n and tasks[indices[cur]][0] <= time:\n",
    "                heapq.heappush(h, (tasks[indices[cur]][1], indices[cur]))\n",
    "                cur += 1\n",
    "            \n",
    "            process, idx = heapq.heappop(h)\n",
    "            time += process\n",
    "            res.append(idx)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        time = 0\n",
    "        i = 0\n",
    "        n = len(tasks)\n",
    "        ans = []\n",
    "        h = []\n",
    "        tasks = sorted(zip(range(n), tasks), key=lambda x: x[1][0])\n",
    "        while len(ans) < n:\n",
    "            while i < n and tasks[i][1][0] <= time:\n",
    "                heapq.heappush(h, (tasks[i][1][1], tasks[i][0]))\n",
    "                i += 1\n",
    "            if not h:\n",
    "                time = tasks[i][1][0]\n",
    "            else:\n",
    "                x = heapq.heappop(h)\n",
    "                time += x[0]\n",
    "                ans.append(x[1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        s_tasks = []\n",
    "        for i in range(len(tasks)):\n",
    "            s_tasks.append((tasks[i][0], tasks[i][1], i))\n",
    "        s_tasks.sort(key=lambda x:x[0])\n",
    "        waiting_line = []\n",
    "        heapq.heapify(waiting_line)\n",
    "        i = 0\n",
    "        clock = s_tasks[0][0]\n",
    "        res = []\n",
    "        while i < len(s_tasks) or len(waiting_line) > 0:\n",
    "            while i < len(s_tasks):\n",
    "                enqueue, span, idx = s_tasks[i]\n",
    "                if enqueue <= clock:\n",
    "                    heapq.heappush(waiting_line, (span, idx))\n",
    "                    i+=1\n",
    "                else:\n",
    "                    break\n",
    "            if len(waiting_line) > 0:\n",
    "                span, idx = heapq.heappop(waiting_line)\n",
    "                res.append(idx)\n",
    "                clock += span\n",
    "            else:\n",
    "                if i < len(s_tasks):\n",
    "                    clock = s_tasks[i][0]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        taskid = list(range(n))\n",
    "        taskid.sort(key=lambda x:tasks[x][0])\n",
    "        tasks.sort(key = lambda x:x[0])\n",
    "        t = 0\n",
    "        i = 0\n",
    "        pq = []\n",
    "        res = []\n",
    "        while pq or i<n:\n",
    "            if len(pq)==0 and i<n and t<tasks[i][0]:\n",
    "                t = tasks[i][0]\n",
    "            while i<n and tasks[i][0]<=t:\n",
    "                heapq.heappush(pq,[tasks[i][1],taskid[i]])\n",
    "                i+=1\n",
    "            process,idx = heapq.heappop(pq)\n",
    "            res.append(idx)\n",
    "            t += process\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "   \n",
    "        n = len(tasks)\n",
    "        s =sorted(range(n), key = lambda i:tasks[i][0])   \n",
    "        stack = []\n",
    "        time = 0\n",
    "        seq = []\n",
    "        i = 0\n",
    "        while len(seq) < n:\n",
    "            if i < n and time < tasks[s[i]][0] and not stack:\n",
    "                time = tasks[s[i]][0]\n",
    "            while i < n and tasks[s[i]][0] <= time:\n",
    "                heapq.heappush(stack, [tasks[s[i]][1],s[i]])\n",
    "                i += 1\n",
    "            tm, u = heapq.heappop(stack)\n",
    "            seq.append(u)\n",
    "            time += tm\n",
    "        return seq\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        s =sorted(range(n), key = lambda i:tasks[i][0])   \n",
    "        stack = []\n",
    "        time = 0\n",
    "        seq = []\n",
    "        i = 0\n",
    "        while len(seq) < n:\n",
    "            if i < n and time < tasks[s[i]][0] and not stack:\n",
    "                time = tasks[s[i]][0]\n",
    "            while i < n and tasks[s[i]][0] <= time:\n",
    "                heapq.heappush(stack, [tasks[s[i]][1],s[i]])\n",
    "                i += 1\n",
    "            tm, u = heapq.heappop(stack)\n",
    "            seq.append(u)\n",
    "            time += tm\n",
    "        return seq\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks):  \n",
    "        n = len(tasks)  \n",
    "        # 把原始索引也添加上，方便后面排序用  \n",
    "        triples = [(tasks[i][0], tasks[i][1], i) for i in range(n)]  \n",
    "        # 数组先按照任务的开始时间排序  \n",
    "        triples.sort(key=lambda x: x[0])  \n",
    "        \n",
    "        # 使用 heapq 来实现 PriorityQueue  \n",
    "        import heapq  \n",
    "        pq = []  \n",
    "  \n",
    "        # 初始化结果列表和完成时间线  \n",
    "        res = []  \n",
    "        now = 0  \n",
    "        i = 0  \n",
    "        while len(res) < n:  \n",
    "            if pq:  \n",
    "                # 完成队列中的一个任务  \n",
    "                triple = heapq.heappop(pq)  \n",
    "                res.append(triple[1])  \n",
    "                # 每完成一个任务，就要推进时间线  \n",
    "                now += triple[0]  \n",
    "            elif i < n and triples[i][0] > now:  \n",
    "                # 队列为空可能因为还没到开始时间，  \n",
    "                # 直接把时间线推进到最近任务的开始时间  \n",
    "                now = triples[i][0]  \n",
    "            # 由于时间线的推进，会产生可以开始执行的任务  \n",
    "            while i < n and triples[i][0] <= now:  \n",
    "                heapq.heappush(pq, (triples[i][1], triples[i][2], triples[i][0]))  \n",
    "                i += 1  \n",
    "        # 将结果列表转换为数组并返回  \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        taskid = list(range(n))\n",
    "        taskid.sort(key = lambda x:tasks[x][0])\n",
    "        tasks.sort(key=lambda x:x[0])\n",
    "        pq,res = [],[]\n",
    "        i,t = 0,0\n",
    "        while pq or i<n:\n",
    "            if not pq:\n",
    "                t = max(tasks[i][0],t)\n",
    "            while i<n and tasks[i][0]<=t:\n",
    "                heapq.heappush(pq,[tasks[i][1],taskid[i]])\n",
    "                i+=1\n",
    "            process,idx = heapq.heappop(pq)\n",
    "            res.append(idx)\n",
    "            t+=process\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        taskid = list(range(n))\n",
    "        taskid.sort(key = lambda x:tasks[x][0])\n",
    "        tasks.sort(key=lambda x:x[0])\n",
    "        pq,res = [],[]\n",
    "        i,t = 0,0\n",
    "        while pq or i<n:\n",
    "            if not pq:\n",
    "                t = max(tasks[i][0],t)\n",
    "            while i<n and tasks[i][0]<=t:\n",
    "                heapq.heappush(pq,[tasks[i][1],taskid[i]])\n",
    "                i+=1\n",
    "            process,idx = heapq.heappop(pq)\n",
    "            res.append(idx)\n",
    "            t+=process\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks):\n",
    "        n = len(tasks)\n",
    "        # 把原始索引也添加上，方便后面排序用\n",
    "        triples = [(tasks[i][0], tasks[i][1], i) for i in range(n)]\n",
    "        # 数组先按照任务的开始时间排序\n",
    "        triples.sort(key=lambda x: x[0])\n",
    "\n",
    "        # 按照任务的处理时间排序，如果处理时间相同，按照原始索引排序\n",
    "        pq = []\n",
    "        res = []\n",
    "        # 记录完成任务的时间线\n",
    "        now = 0\n",
    "        i = 0\n",
    "        while len(res) < n:\n",
    "            while i < n and triples[i][0] <= now:\n",
    "                heapq.heappush(pq, (triples[i][1], triples[i][2]))\n",
    "                i += 1\n",
    "\n",
    "            if pq:\n",
    "                # 完成队列中的一个任务\n",
    "                process_time, original_index = heapq.heappop(pq)\n",
    "                res.append(original_index)\n",
    "                # 每完成一个任务，就要推进时间线\n",
    "                now += process_time\n",
    "            elif i < n:\n",
    "                # 队列为空可能因为还没到开始时间，\n",
    "                # 直接把时间线推进到最近任务的开始时间\n",
    "                now = triples[i][0]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        taskid = list(range(n))\n",
    "        taskid.sort(key = lambda x:tasks[x][0])\n",
    "        tasks.sort(key=lambda x:x[0])\n",
    "        pq,res = [],[]\n",
    "        i,t = 0,0\n",
    "        while pq or i<n:\n",
    "            if not pq:\n",
    "                t = max(tasks[i][0],t)\n",
    "            while i<n and tasks[i][0]<=t:\n",
    "                heapq.heappush(pq,[tasks[i][1],taskid[i]])\n",
    "                i+=1\n",
    "            process,idx = heapq.heappop(pq)\n",
    "            res.append(idx)\n",
    "            t+=process\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        taskid = list(range(n))\n",
    "        taskid.sort(key=lambda x:tasks[x][0])\n",
    "        tasks.sort(key = lambda x:x[0])\n",
    "        t = 0\n",
    "        i = 0\n",
    "        pq = []\n",
    "        res = []\n",
    "        while pq or i<n:\n",
    "            if len(pq)==0 and i<n and t<tasks[i][0]:\n",
    "                t = tasks[i][0]\n",
    "            while i<n and tasks[i][0]<=t:\n",
    "                heapq.heappush(pq,[tasks[i][1],taskid[i]])\n",
    "                i+=1\n",
    "            process,idx = heapq.heappop(pq)\n",
    "            res.append(idx)\n",
    "            t += process\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks):  \n",
    "        n = len(tasks)  \n",
    "        # 把原始索引也添加上，方便后面排序用  \n",
    "        triples = [(tasks[i][0], tasks[i][1], i) for i in range(n)]  \n",
    "        # 数组先按照任务的开始时间排序  \n",
    "        triples.sort(key=lambda x: x[0])  \n",
    "        \n",
    "        # 使用 heapq 来实现 PriorityQueue  \n",
    "        import heapq  \n",
    "        pq = []  \n",
    "  \n",
    "        # 初始化结果列表和完成时间线  \n",
    "        res = []  \n",
    "        now = 0  \n",
    "        i = 0  \n",
    "        while len(res) < n:  \n",
    "            if pq:  \n",
    "                # 完成队列中的一个任务  \n",
    "                triple = heapq.heappop(pq)  \n",
    "                res.append(triple[1])  \n",
    "                # 每完成一个任务，就要推进时间线  \n",
    "                now += triple[0]  \n",
    "            elif i < n and triples[i][0] > now:  \n",
    "                # 队列为空可能因为还没到开始时间，  \n",
    "                # 直接把时间线推进到最近任务的开始时间  \n",
    "                now = triples[i][0]  \n",
    "            # 由于时间线的推进，会产生可以开始执行的任务  \n",
    "            while i < n and triples[i][0] <= now:  \n",
    "                heapq.heappush(pq, (triples[i][1], triples[i][2], triples[i][0]))  \n",
    "                i += 1  \n",
    "        # 将结果列表转换为数组并返回  \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        taskid = list(range(n))\n",
    "        taskid.sort(key = lambda x:tasks[x][0])\n",
    "        #tasks.sort(key=lambda x:x[0])\n",
    "        pq,res = [],[]\n",
    "        i,t = 0,0\n",
    "        while pq or i<n:\n",
    "            if not pq:\n",
    "                #t = max(tasks[i][0],t)\n",
    "                t = max(tasks[taskid[i]][0],t)\n",
    "            #while i<n and tasks[i][0]<=t:\n",
    "            while i<n and tasks[taskid[i]][0]<=t:\n",
    "                heapq.heappush(pq,[tasks[taskid[i]][1],taskid[i]])\n",
    "                i+=1\n",
    "            process,idx = heapq.heappop(pq)\n",
    "            res.append(idx)\n",
    "            t+=process\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        tasks = sorted(enumerate(tasks), key=lambda x: x[1][0])\n",
    "        i, n = 0, len(tasks)\n",
    "        ans = [] \n",
    "        cur = 0 \n",
    "        heap = [] \n",
    "        while len(ans) < n:\n",
    "            while i < n and tasks[i][1][0] <= cur:\n",
    "                heapq.heappush(heap, (tasks[i][1][1], tasks[i][0]))\n",
    "                i += 1\n",
    "            if not heap:\n",
    "                cur = tasks[i][1][0]\n",
    "                continue\n",
    "            time, idx = heapq.heappop(heap)\n",
    "            cur += time\n",
    "            ans.append(idx) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        taskid = list(range(n))\n",
    "        taskid.sort(key = lambda x:tasks[x][0])\n",
    "        tasks.sort(key=lambda x:x[0])\n",
    "        pq,res = [],[]\n",
    "        i,t = 0,0\n",
    "        while pq or i<n:\n",
    "            if not pq:\n",
    "                t = max(tasks[i][0],t)\n",
    "            while i<n and tasks[i][0]<=t:\n",
    "                heapq.heappush(pq,[tasks[i][1],taskid[i]])\n",
    "                i+=1\n",
    "            process,idx = heapq.heappop(pq)\n",
    "            res.append(idx)\n",
    "            t+=process\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks):  \n",
    "        n = len(tasks)\n",
    "        # 把原始索引也添加上，方便后面排序用\n",
    "        triples = [(tasks[i][0], tasks[i][1], i) for i in range(n)]\n",
    "        # 数组先按照任务的开始时间排序\n",
    "        triples.sort(key=lambda x: x[0])\n",
    "\n",
    "        # 使用 heapq 来实现 PriorityQueue\n",
    "        import heapq\n",
    "        pq = []\n",
    "\n",
    "        # 初始化结果列表和完成时间线\n",
    "        res = []\n",
    "        now = 0\n",
    "        i = 0\n",
    "        while len(res) < n:\n",
    "            if pq:\n",
    "                # 完成队列中的一个任务\n",
    "                item = heapq.heappop(pq)\n",
    "                res.append(item[1])\n",
    "                # 每完成一个任务，就要推进时间线\n",
    "                now += item[0]\n",
    "            elif i < n and triples[i][0] > now:\n",
    "                # 队列为空可能因为还没到开始时间，\n",
    "                # 直接把时间线推进到最近任务的开始时间\n",
    "                now = triples[i][0]\n",
    "                # 由于时间线的推进，会产生可以开始执行的任务\n",
    "            while i < n and triples[i][0] <= now:\n",
    "                heapq.heappush(pq, (triples[i][1], triples[i][2], triples[i][0]))\n",
    "                i += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        s_tasks = []\n",
    "        for i in range(len(tasks)):\n",
    "            s_tasks.append((tasks[i][0], tasks[i][1], i))\n",
    "        s_tasks.sort(key=lambda x:x[0])\n",
    "        waiting_line = []\n",
    "        heapq.heapify(waiting_line)\n",
    "        i = 0\n",
    "        clock = s_tasks[0][0]\n",
    "        res = []\n",
    "        while i < len(s_tasks) or len(waiting_line) > 0:\n",
    "            while i < len(s_tasks):\n",
    "                enqueue, span, idx = s_tasks[i]\n",
    "                if enqueue <= clock:\n",
    "                    heapq.heappush(waiting_line, (span, idx))\n",
    "                    i+=1\n",
    "                else:\n",
    "                    break\n",
    "            if len(waiting_line) > 0:\n",
    "                span, idx = heapq.heappop(waiting_line)\n",
    "                res.append(idx)\n",
    "                clock += span\n",
    "            else:\n",
    "                if i < len(s_tasks):\n",
    "                    clock = s_tasks[i][0]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks):  \n",
    "        n = len(tasks)  \n",
    "        # 把原始索引也添加上，方便后面排序用  \n",
    "        triples = [(tasks[i][0], tasks[i][1], i) for i in range(n)]  \n",
    "        # 数组先按照任务的开始时间排序  \n",
    "        triples.sort(key=lambda x: x[0])  \n",
    "        \n",
    "        # 使用 heapq 来实现 PriorityQueue  \n",
    "        import heapq  \n",
    "        pq = []  \n",
    "        # for t in triples:  \n",
    "        #     heapq.heappush(pq, t)  \n",
    "        \n",
    "        # 初始化结果列表和完成时间线  \n",
    "        res = []  \n",
    "        now = 0  \n",
    "        i = 0  \n",
    "        while len(res) < n:  \n",
    "            if pq:  \n",
    "                # 完成队列中的一个任务  \n",
    "                triple = heapq.heappop(pq)  \n",
    "                res.append(triple[1])  \n",
    "                # 每完成一个任务，就要推进时间线  \n",
    "                now += triple[0]  \n",
    "            elif i < n and triples[i][0] > now:  \n",
    "                # 队列为空可能因为还没到开始时间，  \n",
    "                # 直接把时间线推进到最近任务的开始时间  \n",
    "                now = triples[i][0]  \n",
    "            # 由于时间线的推进，会产生可以开始执行的任务  \n",
    "            while i < n and triples[i][0] <= now:  \n",
    "                heapq.heappush(pq, (triples[i][1], triples[i][2], triples[i][0]))  \n",
    "                i += 1  \n",
    "        # 将结果列表转换为数组并返回  \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        idxes = list(range(n))\n",
    "        idxes.sort(key=lambda x: tasks[x][0])\n",
    "\n",
    "        \n",
    "        pq = []\n",
    "        ptr = 0\n",
    "        timestep = 0\n",
    "\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if not pq:\n",
    "                timestep = max(timestep, tasks[idxes[ptr]][0])\n",
    "\n",
    "            while ptr < n and tasks[idxes[ptr]][0] <= timestep:\n",
    "                heapq.heappush(pq, (tasks[idxes[ptr]][1], idxes[ptr]))\n",
    "                ptr += 1\n",
    "\n",
    "            process_time, idx = heapq.heappop(pq)\n",
    "            timestep += process_time\n",
    "            res.append(idx)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        taskid = list(range(n))\n",
    "        taskid.sort(key = lambda x:tasks[x][0])\n",
    "        tasks.sort(key=lambda x:x[0])\n",
    "        pq,res = [],[]\n",
    "        i,t = 0,0\n",
    "        while pq or i<n:\n",
    "            if not pq and t < tasks[i][0]:\n",
    "                t = tasks[i][0]\n",
    "            while i<n and tasks[i][0]<=t:\n",
    "                heapq.heappush(pq,[tasks[i][1],taskid[i]])\n",
    "                i+=1\n",
    "            process,idx = heapq.heappop(pq)\n",
    "            res.append(idx)\n",
    "            t+=process\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n=len(tasks)\n",
    "        a=list(range(n))  #index<=>timestart\n",
    "        a.sort(key=lambda x: tasks[x][0])\n",
    "        time=0\n",
    "        ptr=0\n",
    "        c=list()\n",
    "        q=list()\n",
    "        for i in range(n):\n",
    "            if not q:\n",
    "                time=max(time,tasks[a[ptr]][0])\n",
    "            while ptr<n and tasks[a[ptr]][0]<=time:\n",
    "                heapq.heappush(q, (tasks[a[ptr]][1], a[ptr]))\n",
    "                ptr+=1\n",
    "            proc,index=heapq.heappop(q)\n",
    "            time+=proc\n",
    "            c.append(index)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        tm = list(range(n))\n",
    "        tm.sort(key=lambda x: tasks[x][0])\n",
    "        ans = []\n",
    "        pre = i = 0\n",
    "        stack = []\n",
    "        while len(ans) < n:\n",
    "            while i < n and tasks[tm[i]][0] <= pre:\n",
    "                heapq.heappush(stack, [tasks[tm[i]][1], tm[i]])\n",
    "                i += 1\n",
    "            if not stack:\n",
    "                pre = tasks[tm[i]][0]\n",
    "                continue\n",
    "            cost, ind = heapq.heappop(stack)\n",
    "            ans.append(ind)\n",
    "            pre += cost\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        indexs = list(range(n))\n",
    "        indexs.sort(key = lambda i : tasks[i][0])\n",
    "\n",
    "        res = []\n",
    "        que = []\n",
    "        t = 0\n",
    "        ptr = 0\n",
    "        for i in range(n):\n",
    "            if not que:\n",
    "                t = max(t, tasks[indexs[ptr]][0])\n",
    "            \n",
    "            while ptr < n and t >= tasks[indexs[ptr]][0]:\n",
    "                heapq.heappush(que, [tasks[indexs[ptr]][1], indexs[ptr]])\n",
    "                ptr += 1\n",
    "            \n",
    "            dura, index = heapq.heappop(que)\n",
    "            t += dura\n",
    "            res.append(index)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        pq,res = [],[]\n",
    "        tasksid = list(range(n))\n",
    "        tasksid.sort(key=lambda x:tasks[x][0])\n",
    "        tasks.sort(key=lambda x:x[0])\n",
    "        i,t = 0,0\n",
    "        while pq or i<n:\n",
    "            if not pq:\n",
    "                t = max(t,tasks[i][0])\n",
    "            while i<n and tasks[i][0]<=t:\n",
    "                heapq.heappush(pq,[tasks[i][1],tasksid[i]])\n",
    "                i+=1\n",
    "            process,idx = heapq.heappop(pq)\n",
    "            t+=process\n",
    "            res.append(idx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        gen=((i,e,p) for i,(e,p) in enumerate(tasks))\n",
    "        arr=sorted(gen,key=lambda x:(x[1],x[2],x[0]))\n",
    "        # print(arr)\n",
    "        j,n=1,len(arr)\n",
    "        ans=[]\n",
    "        cur=arr[0][1]\n",
    "        h=[]\n",
    "        h.append((arr[0][2],arr[0][0]))\n",
    "        while h:\n",
    "            needTime,index=heappop(h)\n",
    "            ans.append(index)\n",
    "            cur+=needTime\n",
    "            while j<n and arr[j][1]<=cur: \n",
    "                heappush(h,(arr[j][2],arr[j][0]))\n",
    "                j+=1\n",
    "            if not h and j<n:\n",
    "                heappush(h,(arr[j][2],arr[j][0]))\n",
    "                cur=arr[j][1]\n",
    "                j+=1\n",
    "            # print(h,cur)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        pos = list(range(n))\n",
    "        pos.sort(key = lambda x: tasks[x][0])\n",
    "\n",
    "        ans = []\n",
    "        q = []\n",
    "        time = 0\n",
    "        c = 0\n",
    "        for i in range(n):\n",
    "            if not q: time = max(time, tasks[pos[c]][0])\n",
    "            while c < n and tasks[pos[c]][0] <= time:\n",
    "                heapq.heappush(q, (tasks[pos[c]][1], pos[c]))\n",
    "                c += 1\n",
    "            duration, j = heapq.heappop(q)\n",
    "            time += duration\n",
    "            ans.append(j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        ranked = []\n",
    "        queue = []\n",
    "        result = []\n",
    "        next_task_idx = 0\n",
    "        time = 0\n",
    "        n = len(tasks)\n",
    "\n",
    "        for i in range(n):\n",
    "            enq_time, proc_time = tasks[i]\n",
    "            ranked.append((enq_time, proc_time, i))\n",
    "        ranked.sort(key=lambda x: (x[0], x[2]))\n",
    "\n",
    "        while len(result) < n:\n",
    "            while next_task_idx < n and time >= ranked[next_task_idx][0]:\n",
    "                heapq.heappush(queue, (ranked[next_task_idx][1], ranked[next_task_idx][2]))\n",
    "                next_task_idx += 1\n",
    "          \n",
    "            if queue:\n",
    "                curr_task = heapq.heappop(queue)\n",
    "                time += curr_task[0]\n",
    "                result.append(curr_task[1])\n",
    "            else:\n",
    "                time = ranked[next_task_idx][0]\n",
    "        return result\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 模拟，最小堆\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda x: tasks[x][0])\n",
    "\n",
    "        ans = list()\n",
    "        # 优先队列\n",
    "        q = list()\n",
    "        # 时间戳\n",
    "        timestamp = 0\n",
    "        # 数组上遍历的指针\n",
    "        ptr = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            # 如果没有可以执行的任务，直接快进\n",
    "            if not q:\n",
    "                timestamp = max(timestamp, tasks[indices[ptr]][0])\n",
    "            # 将所有小于等于时间戳的任务放入优先队列\n",
    "            while ptr < n and tasks[indices[ptr]][0] <= timestamp:\n",
    "                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))\n",
    "                ptr += 1\n",
    "            # 选择处理时间最小的任务\n",
    "            process, index = heapq.heappop(q)\n",
    "            timestamp += process\n",
    "            ans.append(index)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda x: tasks[x][0])\n",
    "\n",
    "        ans = list()\n",
    "        # 优先队列\n",
    "        q = list()\n",
    "        # 时间戳\n",
    "        timestamp = 0\n",
    "        # 数组上遍历的指针\n",
    "        ptr = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            # 如果没有可以执行的任务，直接快进\n",
    "            if not q:\n",
    "                timestamp = max(timestamp, tasks[indices[ptr]][0])\n",
    "            # 将所有小于等于时间戳的任务放入优先队列\n",
    "            while ptr < n and tasks[indices[ptr]][0] <= timestamp:\n",
    "                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))\n",
    "                ptr += 1\n",
    "            # 选择处理时间最小的任务\n",
    "            process, index = heapq.heappop(q)\n",
    "            timestamp += process\n",
    "            ans.append(index)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda x: tasks[x][0])\n",
    "\n",
    "        ans = list()\n",
    "        # 优先队列\n",
    "        q = list()\n",
    "        # 时间戳\n",
    "        timestamp = 0\n",
    "        # 数组上遍历的指针\n",
    "        ptr = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            # 如果没有可以执行的任务，直接快进\n",
    "            if not q:\n",
    "                timestamp = max(timestamp, tasks[indices[ptr]][0])\n",
    "            # 将所有小于等于时间戳的任务放入优先队列\n",
    "            while ptr < n and tasks[indices[ptr]][0] <= timestamp:\n",
    "                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))\n",
    "                ptr += 1\n",
    "            # 选择处理时间最小的任务\n",
    "            process, index = heapq.heappop(q)\n",
    "            timestamp += process\n",
    "            ans.append(index)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "\n",
    "        n = len(tasks)\n",
    "        indices = list(range(n))\n",
    "\n",
    "        indices.sort(key = lambda x: tasks[x][0])\n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        q = list()\n",
    "\n",
    "        timestamp = 0\n",
    "\n",
    "        ptr = 0\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            if not q:\n",
    "\n",
    "                timestamp = max(timestamp, tasks[indices[ptr]][0])\n",
    "\n",
    "            while ptr < n and tasks[indices[ptr]][0] <= timestamp:\n",
    "\n",
    "                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))\n",
    "\n",
    "                ptr += 1\n",
    "\n",
    "            process, index = heapq.heappop(q)\n",
    "\n",
    "            timestamp += process\n",
    "\n",
    "            ans.append(index)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        waitting_line = []\n",
    "        heapq.heapify(waitting_line)\n",
    "        processing_item = None\n",
    "        res = []\n",
    "        h_tasks = []\n",
    "        for i in range(len(tasks)):\n",
    "            h_tasks.append((tasks[i][0], i, tasks[i][1]))\n",
    "        heapq.heapify(h_tasks)\n",
    "        cur_time = heapq.nsmallest(1, h_tasks)[0][0]\n",
    "        while len(h_tasks) > 0:\n",
    "            enqueue, i, processing = heapq.heappop(h_tasks)\n",
    "            if enqueue <= cur_time or len(waitting_line) == 0:\n",
    "                if len(waitting_line) == 0:\n",
    "                    cur_time = enqueue\n",
    "                heapq.heappush(waitting_line, (processing, i, enqueue))\n",
    "                continue\n",
    "            while enqueue > cur_time and len(waitting_line) > 0:\n",
    "                processing_item = heapq.heappop(waitting_line)\n",
    "                res.append(processing_item[1])\n",
    "                cur_time += processing_item[0]\n",
    "                if enqueue <= cur_time:\n",
    "                    heapq.heappush(waitting_line, (processing, i, enqueue))\n",
    "            if len(waitting_line) == 0:\n",
    "                heapq.heappush(waitting_line, (processing, i, enqueue))\n",
    "                cur_time = enqueue\n",
    "        while len(waitting_line) > 0:\n",
    "            processing_item = heapq.heappop(waitting_line)\n",
    "            res.append(processing_item[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        idx = list(range(len(tasks)))\n",
    "        idx.sort(key=lambda x: (tasks[x], x))\n",
    "        time = 0\n",
    "        ans = []\n",
    "        waiting = []\n",
    "        for i in idx:\n",
    "            te, tp = tasks[i]\n",
    "            if not waiting:\n",
    "                if te > time:\n",
    "                    time = te + tp\n",
    "                    ans.append(i)\n",
    "                else:\n",
    "                    heappush(waiting, (tp, i))\n",
    "            else:\n",
    "                while waiting and te > time:\n",
    "                    tpj, j = heappop(waiting)\n",
    "                    time += tpj\n",
    "                    ans.append(j)\n",
    "                if te > time:\n",
    "                    time = te + tp\n",
    "                    ans.append(i)\n",
    "                else:\n",
    "                    heappush(waiting, (tp, i))\n",
    "        \n",
    "        while waiting:\n",
    "            _, i = heappop(waiting)\n",
    "            ans.append(i)\n",
    "\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda x: tasks[x][0])\n",
    "\n",
    "        ans = list()\n",
    "        # 优先队列\n",
    "        q = list()\n",
    "        # 时间戳\n",
    "        timestamp = 0\n",
    "        # 数组上遍历的指针\n",
    "        ptr = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            # 如果没有可以执行的任务，直接快进\n",
    "            if not q:\n",
    "                timestamp = max(timestamp, tasks[indices[ptr]][0])\n",
    "            # 将所有小于等于时间戳的任务放入优先队列\n",
    "            while ptr < n and tasks[indices[ptr]][0] <= timestamp:\n",
    "                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))\n",
    "                ptr += 1\n",
    "            # 选择处理时间最小的任务\n",
    "            process, index = heapq.heappop(q)\n",
    "            timestamp += process\n",
    "            ans.append(index)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        arr=[(e,p,i) for i,(e,p) in enumerate(tasks)]\n",
    "        arr.sort()\n",
    "        ans=[]\n",
    "        h=[]\n",
    "        h.append((arr[0][1],arr[0][2]))\n",
    "        j=1\n",
    "        cur=arr[0][0]\n",
    "        while h:\n",
    "            needTime,index=heappop(h)\n",
    "            ans.append(index)\n",
    "            cur+=needTime\n",
    "            while j<len(arr) and arr[j][0]<=cur: \n",
    "                heappush(h,(arr[j][1],arr[j][2]))\n",
    "                j+=1\n",
    "            if not h and j<len(arr):\n",
    "                heappush(h,(arr[j][1],arr[j][2]))\n",
    "                cur=arr[j][0]\n",
    "                j+=1\n",
    "            # print(h,cur)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        indexs = list(range(n))\n",
    "        indexs.sort(key = lambda i : tasks[i][0])\n",
    "\n",
    "        res = []\n",
    "        ptr = 0\n",
    "        que = [[tasks[indexs[ptr]][1], indexs[ptr]]]\n",
    "        \n",
    "        ptr += 1\n",
    "        while ptr < n and tasks[indexs[ptr]][0] == tasks[indexs[ptr - 1]][0]:\n",
    "            que.append([tasks[indexs[ptr]][1], indexs[ptr]])\n",
    "            ptr += 1\n",
    "        \n",
    "        heapq.heapify(que)\n",
    "        t = tasks[que[0][1]][0]\n",
    "        while que or ptr < n:\n",
    "            if que:\n",
    "                dura, index = heapq.heappop(que)\n",
    "                res.append(index)\n",
    "                t += dura\n",
    "            else:\n",
    "                t = max(t, tasks[indexs[ptr]][0])\n",
    "\n",
    "            while ptr < n and t >= tasks[indexs[ptr]][0]:\n",
    "                heapq.heappush(que, [tasks[indexs[ptr]][1], indexs[ptr]])\n",
    "                ptr += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda x:tasks[x][0])\n",
    "        ptr = 0\n",
    "        timestamp = 0\n",
    "        pq = queue.PriorityQueue()\n",
    "        res = list()\n",
    "        for i in range(n):\n",
    "            if pq.empty():\n",
    "                timestamp = max(timestamp, tasks[indices[ptr]][0])\n",
    "            while ptr < n and tasks[indices[ptr]][0] <= timestamp:\n",
    "                pq.put((tasks[indices[ptr]][1], indices[ptr]))\n",
    "                ptr += 1\n",
    "            time, index = pq.get()\n",
    "            timestamp += time\n",
    "            res.append(index)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        orders, queue, result, n, cur, idx = sorted(list(range(len(tasks))), key=lambda x: tasks[x][0]), [], deque(), len(tasks), 0, 0\n",
    "        for i in range(n):\n",
    "            if not queue:\n",
    "                cur = max(cur, tasks[orders[idx]][0])\n",
    "            while idx < n and tasks[orders[idx]][0] <= cur:\n",
    "                heappush(queue, (tasks[orders[idx]][1], orders[idx]))\n",
    "                idx += 1\n",
    "            process, r = heappop(queue)\n",
    "            cur += process\n",
    "            result.append(r)\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda x: tasks[x][0])\n",
    "\n",
    "        ans = list()\n",
    "        # 优先队列\n",
    "        q = list()\n",
    "        # 时间戳\n",
    "        timestamp = 0\n",
    "        # 数组上遍历的指针\n",
    "        ptr = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            # 如果没有可以执行的任务，直接快进\n",
    "            if not q:\n",
    "                timestamp = max(timestamp, tasks[indices[ptr]][0])\n",
    "            # 将所有小于等于时间戳的任务放入优先队列\n",
    "            while ptr < n and tasks[indices[ptr]][0] <= timestamp:\n",
    "                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))\n",
    "                ptr += 1\n",
    "            # 选择处理时间最小的任务\n",
    "            process, index = heapq.heappop(q)\n",
    "            timestamp += process\n",
    "            ans.append(index)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        waitting_line = []\n",
    "        heapq.heapify(waitting_line)\n",
    "        processing_item = None\n",
    "        \n",
    "        res = []\n",
    "        h_tasks = []\n",
    "        for i in range(len(tasks)):\n",
    "            h_tasks.append((tasks[i][0], i, tasks[i][1]))\n",
    "        heapq.heapify(h_tasks)\n",
    "        cur_time = heapq.nsmallest(1, h_tasks)[0][0]\n",
    "        while len(h_tasks) > 0:\n",
    "            enqueue, i, processing = heapq.heappop(h_tasks)\n",
    "            #print(enqueue, processing, i, cur_time)\n",
    "            if enqueue <= cur_time or len(waitting_line) == 0:\n",
    "                if len(waitting_line) == 0:\n",
    "                    cur_time = enqueue\n",
    "                heapq.heappush(waitting_line, (processing, i, enqueue))\n",
    "                continue\n",
    "            #print(enqueue, cur_time, i)\n",
    "            while enqueue > cur_time and len(waitting_line) > 0:\n",
    "                #print(waitting_line)\n",
    "                processing_item = heapq.heappop(waitting_line)\n",
    "                #print(processing_item)\n",
    "                res.append(processing_item[1])\n",
    "                cur_time += processing_item[0]\n",
    "                #print(enqueue, cur_time, i)\n",
    "                if enqueue <= cur_time:\n",
    "                    heapq.heappush(waitting_line, (processing, i, enqueue))\n",
    "            if len(waitting_line) == 0:\n",
    "                heapq.heappush(waitting_line, (processing, i, enqueue))\n",
    "                cur_time = enqueue\n",
    "            \n",
    "\n",
    "        #print(waitting_line) \n",
    "        while len(waitting_line) > 0:\n",
    "            processing_item = heapq.heappop(waitting_line)\n",
    "            res.append(processing_item[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        ready = []\n",
    "        ts = 0\n",
    "        ret = []\n",
    "        wait = [(tasks[i][0], i) for i in range(len(tasks))]\n",
    "        heapify(wait)\n",
    "        while ready or wait:\n",
    "            while wait and wait[0][0] <= ts:\n",
    "                i = heappop(wait)[1]\n",
    "                heappush(ready, [tasks[i][1], i])  \n",
    "            if ready:\n",
    "                i = heappop(ready)[1]\n",
    "                ret.append(i)\n",
    "                ts += tasks[i][1]\n",
    "            else:\n",
    "                ts = wait[0][0]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        tasks = [(start, dur, i) for i, (start, dur) in enumerate(tasks)]\n",
    "        tasks.sort(reverse=True)\n",
    "        waiting = []\n",
    "        curr = 0\n",
    "        ans = []\n",
    "        while True:\n",
    "            while tasks and tasks[-1][0] <= curr:\n",
    "                start, dur, idx = tasks.pop()\n",
    "                heappush(waiting, (dur, idx))\n",
    "            \n",
    "            if waiting:\n",
    "                dur, idx = heappop(waiting)\n",
    "                curr += dur\n",
    "                ans.append(idx)\n",
    "            \n",
    "            else:\n",
    "                if tasks:\n",
    "                    curr = tasks[-1][0]\n",
    "                else:\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda x: tasks[x][0])\n",
    "\n",
    "        ans = list()\n",
    "        q = list()\n",
    "        timestamp = 0\n",
    "        ptr = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            if not q:\n",
    "                timestamp = max(timestamp, tasks[indices[ptr]][0])\n",
    "            while ptr < n and tasks[indices[ptr]][0] <= timestamp:\n",
    "                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))\n",
    "                ptr += 1\n",
    "            process, index = heapq.heappop(q)\n",
    "            timestamp += process\n",
    "            ans.append(index)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        res=[]\n",
    "        timestamp = 0\n",
    "        q = []\n",
    "        i = 0\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key = lambda x : tasks[x][0])\n",
    "        while len(res)<n:\n",
    "            if not q:\n",
    "                timestamp = max(timestamp,tasks[indices[i]][0])\n",
    "            while i<n and tasks[indices[i]][0]<=timestamp:\n",
    "                heapq.heappush(q,(tasks[indices[i]][1],indices[i]))\n",
    "                i+=1\n",
    "            if q:\n",
    "                last,idx = heapq.heappop(q)\n",
    "                res.append(idx)\n",
    "                timestamp += last\n",
    "       \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        list1=list(range(len(tasks)))\n",
    "        list1.sort(key=lambda x:tasks[x][0])\n",
    "        timetemp = 0 \n",
    "        ptr =0\n",
    "        pd = queue.PriorityQueue()\n",
    "        res = []\n",
    "        for i in range(len(tasks)):\n",
    "            if pd.empty():\n",
    "                timetemp = max(timetemp,tasks[list1[ptr]][0])\n",
    "            while ptr< len(tasks) and tasks[list1[ptr]][0]<=timetemp:\n",
    "                pd.put([tasks[list1[ptr]][1],list1[ptr]])\n",
    "                ptr=ptr+1\n",
    "            time,index = pd.get()\n",
    "            timetemp = timetemp + time\n",
    "            res.append(index)\n",
    "        return res\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        tasks = [(start, dur, i) for i, (start, dur) in enumerate(tasks)]\n",
    "        tasks.sort(reverse=True)  \n",
    "        print(tasks) \n",
    "        waiting = []\n",
    "        ans = []\n",
    "        curr = tasks[-1][0]\n",
    "        while True:\n",
    "            while tasks and tasks[-1][0] <= curr:\n",
    "                _, dur, i = tasks.pop()\n",
    "                heappush(waiting, (dur, i))\n",
    "            if waiting:\n",
    "                dur, idx = heappop(waiting)\n",
    "                curr = curr + dur\n",
    "                ans.append(idx)\n",
    "            else:\n",
    "                if tasks:\n",
    "                    curr = tasks[-1][0]\n",
    "                else:\n",
    "                    break\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        tasks = sorted([(t[0], t[1], i) for i, t in enumerate(tasks)])\n",
    "        i = 0\n",
    "        h = []\n",
    "        time = tasks[0][0]\n",
    "        while len(res) < len(tasks):\n",
    "            while (i < len(tasks)) and (tasks[i][0] <= time):\n",
    "                heapq.heappush(h, (tasks[i][1], tasks[i][2])) # (processing_time, original_index)\n",
    "                i += 1\n",
    "            if h:\n",
    "                t_diff, original_index = heapq.heappop(h)\n",
    "                time += t_diff\n",
    "                res.append(original_index)\n",
    "            elif i < len(tasks):\n",
    "                time = tasks[i][0]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        # 纯模拟题好吧，用一个堆就能解决问题\n",
    "        tasks = [(s, p, i) for i, (s, p) in enumerate(tasks)]\n",
    "        tasks.sort(reverse=True)\n",
    "        t = 0\n",
    "        h = []\n",
    "        ans = []\n",
    "\n",
    "        while tasks or h:\n",
    "            if not h and tasks[-1][0] > t:\n",
    "                t = tasks[-1][0]\n",
    "            while tasks and tasks[-1][0] <= t:\n",
    "                s, p, i = tasks.pop()\n",
    "                heappush(h, [p, i, s])\n",
    "            p, i, s = heappop(h)\n",
    "            ans.append(i)\n",
    "            t += p\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda x:tasks[x][0])\n",
    "        ptr = 0\n",
    "        timestamp = 0\n",
    "        \n",
    "        pq = queue.PriorityQueue()\n",
    "        res = list()\n",
    "\n",
    "        for i in range(n):\n",
    "            if pq.empty():\n",
    "                timestamp = max(timestamp, tasks[indices[ptr]][0])\n",
    "            while ptr < n and tasks[indices[ptr]][0] <= timestamp:\n",
    "                pq.put((tasks[indices[ptr]][1], indices[ptr]))\n",
    "                ptr += 1\n",
    "            time, index = pq.get()\n",
    "            timestamp += time\n",
    "            res.append(index)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda x:tasks[x][0])\n",
    "        ptr = 0\n",
    "        timestamp = 0\n",
    "        \n",
    "        pq = queue.PriorityQueue()\n",
    "        res = list()\n",
    "\n",
    "        for i in range(n):\n",
    "            if pq.empty():\n",
    "                timestamp = max(timestamp, tasks[indices[ptr]][0])\n",
    "            while ptr < n and tasks[indices[ptr]][0] <= timestamp:\n",
    "                pq.put((tasks[indices[ptr]][1], indices[ptr]))\n",
    "                ptr += 1\n",
    "            time, index = pq.get()\n",
    "            timestamp += time\n",
    "            res.append(index)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda it: tasks[it][0])\n",
    "        stack = []\n",
    "        tm = 0\n",
    "        ans = []\n",
    "        i = 0\n",
    "\n",
    "        while i<n or stack:\n",
    "            while i < n and tasks[ind[i]][0] <= tm:\n",
    "                heappush(stack, [tasks[ind[i]][1], ind[i]])\n",
    "                i += 1\n",
    "            if stack:\n",
    "                x, j = heappop(stack)\n",
    "                ans.append(j)\n",
    "                tm += x\n",
    "            else:\n",
    "                tm = tasks[ind[i]][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        idxed_tasks = sorted(enumerate(tasks), key=lambda x: (x[1][0], x[0]))\n",
    "        q = list()\n",
    "        time = 0\n",
    "        ptr = 0\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if not q:\n",
    "                time = max(idxed_tasks[ptr][1][0], time)\n",
    "            while ptr < n and idxed_tasks[ptr][1][0] <= time:\n",
    "                heappush(q, (idxed_tasks[ptr][1][1], idxed_tasks[ptr][0]))\n",
    "                ptr += 1\n",
    "            t, idx = heappop(q)\n",
    "            time += t\n",
    "            ans.append(idx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        waitting_line = []\n",
    "        heapq.heapify(waitting_line)\n",
    "        processing_item = None\n",
    "        res = []\n",
    "        s_tasks = []\n",
    "        for i in range(len(tasks)):\n",
    "            s_tasks.append((tasks[i][0], i, tasks[i][1]))\n",
    "        s_tasks.sort(key=lambda x:x[0])\n",
    "        cur_time = s_tasks[0][0]\n",
    "        i = 0\n",
    "        while i < len(s_tasks) or len(waitting_line) > 0:\n",
    "            while i < len(s_tasks):\n",
    "                enqueue, idx, processing = s_tasks[i]\n",
    "                if enqueue <= cur_time:\n",
    "                    heapq.heappush(waitting_line, (processing, idx, enqueue))\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            if len(waitting_line) > 0:\n",
    "                processing_item = heapq.heappop(waitting_line)\n",
    "                res.append(processing_item[1])\n",
    "                cur_time += processing_item[0]\n",
    "            else:\n",
    "                cur_time = enqueue\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "   \n",
    "        n = len(tasks)\n",
    "        s =sorted(range(n), key = lambda i:tasks[i][0])\n",
    "        \n",
    "        \n",
    "        stack = []\n",
    "        time = 0\n",
    "        seq = []\n",
    "        i = 0\n",
    "        seq2= []\n",
    "        while len(seq) < n:\n",
    "\n",
    "            if i < n and time < tasks[s[i]][0] and not stack:\n",
    "                time = tasks[s[i]][0]\n",
    "            while i < n and tasks[s[i]][0] <= time:\n",
    "                heapq.heappush(stack, [tasks[s[i]][1],s[i]])\n",
    "                i += 1\n",
    "            #print(stack)\n",
    "            \n",
    "            tm, u = heapq.heappop(stack)\n",
    "            seq.append(u)\n",
    "            seq2.append([u,time])\n",
    "            time += tm\n",
    "        print(seq2)\n",
    "        return seq\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        h = []\n",
    "        arr = []\n",
    "        for pos, (start, last) in enumerate(tasks):\n",
    "            arr.append([start, last, pos])\n",
    "        arr.sort()\n",
    "        ans = []\n",
    "        now_time = 0\n",
    "        cnt = 0\n",
    "        n = len(tasks)\n",
    "        while cnt < n or h:\n",
    "            if not h:\n",
    "                now_time = max(now_time, arr[cnt][0])\n",
    "            while cnt < n and arr[cnt][0] <= now_time:\n",
    "                heappush(h, (arr[cnt][1], arr[cnt][2]))\n",
    "                cnt += 1\n",
    "            # print(h)\n",
    "            new_time, pos = heappop(h)\n",
    "            ans.append(pos)\n",
    "            now_time += new_time\n",
    "            # print(now_time, ans, h)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "\n",
    "        tasks = [tasks[i] + [i,] for i in range(len(tasks))]\n",
    "        tasks = sorted(tasks, key= lambda x: x[0])\n",
    "\n",
    "        que = []\n",
    "        ans = []\n",
    "\n",
    "        i = 0\n",
    "        e_t = 0\n",
    "\n",
    "        while que or i < len(tasks):\n",
    "\n",
    "            if not que:\n",
    "                e_t = max(e_t, tasks[i][0])\n",
    "\n",
    "            while i < len(tasks) and (tasks[i][0] <= e_t):\n",
    "                heapq.heappush(que, (tasks[i][1], tasks[i][2]))\n",
    "                i += 1\n",
    "\n",
    "\n",
    "            u_t, idx = heapq.heappop(que)\n",
    "            ans.append(idx)\n",
    "            e_t = e_t + u_t\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        dic={}\n",
    "        tasks=[tasks[i]+[i] for i in range(len(tasks))]\n",
    "\n",
    "        '''for i in range(len(tasks)):\n",
    "            t=tuple(tasks[i])\n",
    "            if t not in dic:\n",
    "                dic[t]=[i]\n",
    "            else:\n",
    "                dic[t].append(i)'''\n",
    "\n",
    "        tasks=sorted(tasks,key=lambda x:(x[0],x[1]))\n",
    "        ans=[]\n",
    "        queue=[]\n",
    "        heapq.heapify(queue)\n",
    "        i=0\n",
    "        flag={}\n",
    "        while i in range(len(tasks)):\n",
    "            if i==0:\n",
    "                ans.append(tasks[i][2])\n",
    "                cur=tasks[i][0]+tasks[i][1]\n",
    "                i+=1\n",
    "            else:\n",
    "                if cur>=tasks[i][0]:\n",
    "                    heapq.heappush(queue,(tasks[i][1],tasks[i][2]))\n",
    "                    i+=1\n",
    "                else:\n",
    "                    if queue:\n",
    "                        a,b=heapq.heappop(queue)\n",
    "                        cur+=a\n",
    "                        ans.append(b)\n",
    "                    else:\n",
    "                        cur=tasks[i][0]+tasks[i][1]\n",
    "                        ans.append(tasks[i][2])\n",
    "                        i+=1\n",
    "\n",
    "        while queue:\n",
    "            a,b=heapq.heappop(queue)\n",
    "            ans.append(b)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        n = len(tasks)\n",
    "        s = [[0]*3 for _ in range(n)]\n",
    "        for i,(x,y) in enumerate(tasks):\n",
    "            s[i] = [x,y,i]\n",
    "        s.sort()\n",
    "        h = []\n",
    "        heapify(h)\n",
    "        t = s[0][0]\n",
    "        idx = 0\n",
    "        i = 0\n",
    "        ans = [0]*n\n",
    "        while i < n:\n",
    "            while idx < n and s[idx][0] <= t:\n",
    "                heappush(h,(s[idx][1],s[idx][2],s[idx][0]))\n",
    "                idx += 1\n",
    "            if not h:\n",
    "                t = s[idx][0]\n",
    "                continue\n",
    "            v = heappop(h)\n",
    "            t += v[0]\n",
    "            ans[i] = v[1]\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        tasks = sorted([tasks[i] + [i] for i in range(len(tasks))])\n",
    "        heap, res, time, pres = [], [], tasks[0][0], 0\n",
    "        while pres < len(tasks) or heap:\n",
    "            while pres < len(tasks) and tasks[pres][0] <= time:\n",
    "                heappush(heap, tasks[pres][1:])\n",
    "                pres += 1\n",
    "            nextTask = heappop(heap)\n",
    "            res.append(nextTask[1])\n",
    "            time += nextTask[0]\n",
    "            if not heap and pres < len(tasks) and tasks[pres][0] > time:\n",
    "                time = tasks[pres][0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        import heapq\n",
    "        n = len(tasks)\n",
    "        for i in range(0,n):\n",
    "            tasks[i].append(i)\n",
    "        tasks.sort()\n",
    "        \n",
    "        state = []\n",
    "        res = []\n",
    "        t = 0\n",
    "        i = 0\n",
    "        while i < n or len(state) > 0:\n",
    "            if len(state) == 0:    #此时队列空闲 直接顺延到当前最新时间\n",
    "                t = tasks[i][0]\n",
    "                while i < n:\n",
    "                    if tasks[i][0] == t:\n",
    "                        heapq.heappush(state,(tasks[i][1], tasks[i][2])) \n",
    "                        i += 1\n",
    "                    else:\n",
    "                        break\n",
    "            else:\n",
    "                value = heapq.heappop(state)\n",
    "                res.append(value[1])\n",
    "                t += value[0]\n",
    "            \n",
    "                #查看时间更新后 是否有新的任务加入\n",
    "                while i < n:\n",
    "                    if tasks[i][0] <= t:\n",
    "                        heapq.heappush(state,(tasks[i][1], tasks[i][2])) \n",
    "                        i += 1\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, ts: List[List[int]]) -> List[int]:\n",
    "        import heapq\n",
    "        n = len(ts)\n",
    "        # 将 ts 转存成 nts，保留任务编号\n",
    "        nts = [[ts[i][0], ts[i][1], i] for i in range(n)]\n",
    "        # 根据任务入队时间进行排序\n",
    "        nts.sort(key=lambda a: a[0])\n",
    "        print(nts)\n",
    "        # 根据题意，先按照「持续时间」排序，再根据「任务编号」排序\n",
    "        q = []\n",
    "        ans = [0] * n\n",
    "        \n",
    "        time, j, idx = 1, 0, 0\n",
    "        while idx < n:\n",
    "            # 如果当前任务可以添加到「队列」中（满足入队时间）则进行入队\n",
    "            while j < n and nts[j][0] <= time:\n",
    "                heapq.heappush(q, (nts[j][1], nts[j][2]))\n",
    "                j += 1\n",
    "            \n",
    "            if not q:\n",
    "                # 如果当前「队列」没有任务，直接跳到下个任务的入队时间\n",
    "                time = nts[j][0]\n",
    "            else:\n",
    "                # 如果有可执行任务的话，根据优先级将任务出队（记录下标），并跳到该任务完成时间点\n",
    "                cur = heapq.heappop(q)\n",
    "                ans[idx] = cur[1]\n",
    "                time += cur[0]\n",
    "                idx += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "\n",
    "        minHeap = []\n",
    "        \n",
    "        for i in range(len(tasks)):\n",
    "            tasks[i].append(i)\n",
    "        tasks.sort()\n",
    "        tasks = deque(tasks)\n",
    "\n",
    "  \n",
    "\n",
    "        res = []\n",
    "        time = 1\n",
    "        while tasks or minHeap:\n",
    "            while tasks and tasks[0][0] <= time:\n",
    "                t = tasks.popleft()\n",
    "                heappush(minHeap, (t[1], t[2])) #t[1] = processing time, t[2] = idx\n",
    "            if minHeap:\n",
    "                processingtime,idx = heappop(minHeap)\n",
    "                time += processingtime\n",
    "                res.append(idx)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            else:\n",
    "                time = tasks[0][0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Solution:\n",
    "    def getOrder(self, tasks: List[List[int]]) -> List[int]:\n",
    "        i, l = 0, len(tasks)\n",
    "        tmp = [[tasks[i][0], tasks[i][1], i] for i in range(l)]\n",
    "        tmp.sort()\n",
    "        available_tasks = []\n",
    "        res = []\n",
    "        cur_time = 0\n",
    "        while i < l or available_tasks:\n",
    "            # push tasks availble at current time\n",
    "            while i < l and tmp[i][0] <= cur_time:\n",
    "                heappush(available_tasks, [tmp[i][1], tmp[i][2]])\n",
    "                i += 1\n",
    "\n",
    "            if available_tasks:\n",
    "                process_time, task_idx = heappop(available_tasks)\n",
    "                cur_time += process_time\n",
    "                res.append(task_idx)\n",
    "            elif i < l:\n",
    "                cur_time = tmp[i][0]\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
